#include<iostream>
#include "DGraph.h"
#include<stack>
#include<queue>
using namespace std;

istream &operator>>(istream &input, DGraph &DG) {
	ArcNode* ptr;
	int n = DG.getVexnum();
	for (int i = 0; i < n; ++i) {
		ptr = DG.getSerial()[i].getNext();
		ArcNode *pt;
		while (ptr != nullptr) {
			pt = ptr->getNext();
			delete ptr;
			ptr = pt;
		}
	}
	delete[] DG.getSerial();
	DG.setSerial(nullptr);
	
	int vexnum, arcnum;
	cout << "please input the number of vertex and arc: ";
	input >> vexnum >> arcnum;

	DG.setVexnum(vexnum);
	DG.setArcnum(arcnum);
	DG.setGkind(D);

	ptr = new ArcNode[vexnum];
	if (ptr == nullptr) {
		perror("Failed to allocate memory!");
		exit(EXIT_FAILURE);
	}
	DG.setSerial(ptr);
	for (int i = 0; i < vexnum; ++i) {
		ptr[i].setIndex(i);
	}

	cout << "Please input arcs,like this: 1 2;\nit means that there is an arc from vex 1 to vex 2" << endl;
	int num = arcnum;
	int v1, v2;
	ArcNode *pt;
	while (num--) {
		input >> v1 >> v2;
		--v1; --v2;

		pt = &ptr[v1];
		while (pt->getNext() != nullptr) {
			pt = pt->getNext();
		}

		pt->setNext(new ArcNode);
		if (pt->getNext() == nullptr) {
			perror("Failed to allocate memory!");
			exit(EXIT_FAILURE);
		}
		pt->getNext()->setIndex(v2);
	}
	return input;
}
ostream &operator<<(ostream &output, DGraph &DG) {
	ArcNode *pt, *ptr = DG.getSerial();
	int n = DG.getVexnum();
	for (int i = 0; i < n; ++i) {
		output << ptr[i].getIndex() + 1 << "\t";
		pt = ptr[i].getNext();
		while (pt != nullptr) {
			output << pt->getIndex() + 1 << "  ";
			pt = pt->getNext();
		}
		output << endl;
	}
	return output;
}

DGraph::DGraph(int vexnum, int arcnum){
	
	this->setVexnum(vexnum);
	this->setArcnum(arcnum);
	this->setGkind(D);

	ArcNode *ptr = new ArcNode[vexnum];
	if (ptr == nullptr) {
		perror("Failed to allocate memory!");
		exit(EXIT_FAILURE);
	}
	this->setSerial(ptr);
	for (int i = 0; i < vexnum; ++i) {
		ptr[i].setIndex(i);
	}

	cout << "Please input arcs,like this: 1 2;\nit means that there is an arc from vex 1 to vex 2" << endl;
	int num = arcnum;
	int v1, v2;
	ArcNode *pt;
	while (num--) {
		cin >> v1 >> v2;
		--v1; --v2;

		pt = &ptr[v1];
		while (pt->getNext() != nullptr) {
			pt = pt->getNext();
		}

		pt->setNext(new ArcNode);
		if (pt->getNext() == nullptr) {
			perror("Failed to allocate memory!");
			exit(EXIT_FAILURE);
		}
		pt->getNext()->setIndex(v2);
	}
}

DGraph::~DGraph(){
	ArcNode* ptr;
	int n = this->getVexnum();
	for (int i = 0; i < n; ++i) {
		ptr = this->getSerial()[i].getNext();
		ArcNode *pt;
		while (ptr != nullptr) {
			pt = ptr->getNext();
			delete ptr;
			ptr = pt;
		}
	}
	delete[] this->getSerial();
	this->setSerial(nullptr);
}

Status DGraph::BFTraverse(){
	int vexnum = this->getVexnum();
	bool *sign = new bool[vexnum];
	if (sign == nullptr) {
		perror("Failed to allocate memory!");
		exit(EXIT_FAILURE);
	}
	for (int i = 0; i < vexnum; ++i)
		sign[i] = true;

	ArcNode *ptr = this->getSerial();
	queue<int> Queue;
	int n = vexnum;
	while (n > 0) {
		for (int i = 0; i < vexnum; ++i) {
			if (sign[i]) {
				if (Queue.empty()) {
					Queue.push(i);
					sign[i] = false;
					--n;
				}
				while (!Queue.empty()) {
					int temp = Queue.front();
					Queue.pop();
					cout << temp << endl;
					int index = -1;
					ArcNode *pt = ptr[temp].getNext();
					while (pt != nullptr) {
						index = pt->getIndex();
						if (sign[index]) {
							sign[index] = false;
							--n;
							Queue.push(index);
						}
						pt = pt->getNext();
					}
				}
			}
		}
	}
	return OK;
}

Status DGraph::DFTraverse(){
	int vexnum = this->getVexnum();
	bool *sign = new bool[vexnum];
	if (sign == nullptr) {
		perror("Failed to allocate memory!");
		exit(EXIT_FAILURE);
	}
	for (int i = 0; i < vexnum; ++i) 
		sign[i] = true;

	ArcNode *ptr = this->getSerial();
	stack<int> Stack;
	int n = vexnum;
	while (n > 0) {
		for (int i = 0; i < vexnum; ++i) {
			if (sign[i]) {
				if (Stack.empty()) {
					Stack.push(i);
					sign[i] = false;
					--n;
				}
				while (!Stack.empty()) {
					int temp = Stack.top();
					Stack.pop();
					cout << temp << endl;
					int index = -1;
					ArcNode *pt = ptr[temp].getNext();
					while (pt != nullptr) {
						index = pt->getIndex();
						if (sign[index]) {
							sign[index] = false;
							--n;
							Stack.push(index);
						}
						pt = pt->getNext();
					}
				}
			}
		}
	}
	return OK;
}

bool DGraph::ispathBF(int v1, int v2) {
	bool flag = false;
	--v1; --v2;
	const int vexnum = this->getVexnum();
	bool *sign = new bool[vexnum];
	if (sign == nullptr) {
		perror("Failed to allocate memory!");
		exit(EXIT_FAILURE);
	}
	for (int i = 0; i < vexnum; ++i) {
		sign[i] = true;
	}
	ArcNode *ptr = this->getSerial();
	queue<int> Queue;
	Queue.push(v1);
	sign[v1] = false;
	int temp, index = -1;
	while (!Queue.empty()) {
		temp = Queue.front();
		Queue.pop();
		ArcNode *pt = ptr[temp].getNext();
		while (pt != nullptr) {
			index = pt->getIndex();
			if (index == v2) {
				flag = true;
				break;
			}
			if (sign[index]) {
				sign[index] = false;
				Queue.push(index);
			}
			pt = pt->getNext();
		}
		if (flag == true)
			break;
	}

	return flag;
}

bool DGraph::ispathDF(int v1, int v2){
	bool flag = false;
	--v1; --v2;
	const int vexnum = this->getVexnum();
	bool *sign = new bool[vexnum];
	if (sign == nullptr) {
		perror("Failed to allocate memory!");
		exit(EXIT_FAILURE);
	}
	for (int i = 0; i < vexnum; ++i) {
		sign[i] = true;
	}
	ArcNode *ptr = this->getSerial();
	stack<int> Stack;
	Stack.push(v1);
	sign[v1] = false;
	int temp,index = -1;
	while (!Stack.empty()) {
		temp = Stack.top();
		Stack.pop();
		ArcNode *pt = ptr[temp].getNext();
		while (pt != nullptr) {
			index = pt->getIndex();
			if (index == v2) {
				flag = true;
				break;
			}
			if (sign[index]) {
				sign[index] = false;
				Stack.push(index);
			}
			pt = pt->getNext();
		}
		if (index == v2)
			break;
	}

	return flag;
}

Status DGraph::setSerial(ArcNode *serial){
	m_pSerial = serial;
	return OK;
}

ArcNode * DGraph::getSerial(){
	return m_pSerial;
}
